package main

import "fmt"

/*
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]

提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
*/

func letterCombinations(digits string) []string {
	lenth := len(digits)
	if lenth == 0 || lenth > 4 {
		return nil
	}
	digitsMap := [10]string{
		"",     // 0
		"",     // 1
		"abc",  // 2
		"def",  // 3
		"ghi",  // 4
		"jkl",  // 5
		"mno",  // 6
		"pqrs", // 7
		"tuv",  // 8
		"wxyz", // 9
	}
	res := make([]string, 0)
	//index表示第几个数字
	recursion("", digits, 0, digitsMap, &res)
	return res
}

//递归+回溯
func recursion(tempString, digits string, Index int, digitsMap [10]string, res *[]string) {
	//index表示第几个数字
	if len(tempString) == len(digits) { //终止条件，字符串长度等于digits的长度
		*res = append(*res, tempString)
		return
	}
	tmpK := digits[Index] - '0' // 将index指向的数字转为int（确定下一个数字）
	letter := digitsMap[tmpK]   // 取数字对应的字符集
	for i := 0; i < len(letter); i++ {
		tempString = tempString + string(letter[i]) //拼接结果
		recursion(tempString, digits, Index+1, digitsMap, res)
		tempString = tempString[:len(tempString)-1] //回溯
	}
}

func main() {
	fmt.Println(letterCombinations("253"))
}
